This invention relates to the class of error-correcting codes known as Low-Density Parity-Check (LDPC) codes, and more particularly to a set of such codes whose parity-check matrices have irregular column or irregular row weighting, or both, and have a pseudo-random structure. The use of such codes has particular advantages for a two-way communications system employed in an electrical power distribution network.
It is well-known in the art to encode information transmitted over digital communication channels to enable the detection and/or correction of errors by the receiver. Various techniques are employed to add redundancy to a transmitted message. Parity-check codes are a type of code where the redundant information is derived from the message by performing summations or parity checks on the bits of the message. Errors in transmission can be detected by repeating these summations at the receiver, and comparing the results to the parity checks computed by the transmitter. If it is found that information has been corrupted or lost, some types of parity-check codes have decoding procedures that allow the receiver to correct errors introduced by the channel, or restore what has been lost. For this purpose, there are a number of parity check codes available each of which has certain advantages over other codes. Recent research has found that parity-check codes whose parity checks are relatively sparse—that is, each parity check bit is a sum of relatively few message bits—perform particularly well with iterative decoding methods. These codes are known as low-density parity-check or LDPC codes.
Unlike most parity-check codes, LDPC codes are described mainly by their parity-check or decoding matrices, rather than by their encoding matrices. Parity-check matrices derived from random constructions tend to perform quite well, but the resulting encoders tend to be expensive to implement. On the other hand, parity-check matrices with a definite structure result in simple encoders, but do not always have good decoding properties. Many of these structured codes have regular row and column weight (the number of 1s in every row or column of the parity-check matrix is identical), but recent research has demonstrated that codes with irregular row and column weight often leads to improved error correction capability. One type of structured LDPC code with a very simple encoder is a block-cyclic code where the parity-check matrix consists of blocks each of which have a cyclic structure. These codes often have regular row and column weight, but a recent article by S. Johnson and S. Weller, “A Family of Irregular LDPC Codes with Low Encoding Complexity,” IEEE Communications Letters, vol. 7, pp. 79-81, Feb. 2003, demonstrates a way to construct block-cyclic LDPC codes with irregular column weight that outperform similar codes with regular column weight. However, their approach has a limited range in its allowable weight distribution, and does not allow for an irregular row weight.
Many power distribution systems now employ the TWACS® system to send and receive messages over electrical power lines to acquire information on the status of power users including current power usage. In an effort to improve the communications capability of a TWACS®, research has been done on LPDC error control codes. This research has shown that the encoders for typical randomly constructed LDPC codes exceed the storage and computation requirements of TWACS® transmitters.
The present invention is directed to a family of irregular LDPC codes having a pseudo-random structure and low encoding complexity. The family of codes described allows for both irregular column and irregular row weight and provides a broader range of weight distribution than the codes described by Johnson and Weller. In addition, the family allows block-cyclic LDPC codes to have a pseudo-random structure.